package com.fs.leetcode.shuzu.cuowujihe;

import java.util.Collections;
import java.util.HashMap;
import java.util.Map;

/**
 * @author huyunqiang
 * @Date 2019/12/27 9:04
 */
public class SolutionList {

    /**
     * 给定一个数组 nums 代表了集合 S 发生错误后的结果。你的任务是首先寻找到重复出现的整数，
     * 再找到丢失的整数，将它们以数组的形式返回。
     * 输入: nums = [1,2,2,4]
     * 输出: [2,3]
     * @param nums
     * @return
     */
    public  int[] findErrorNums(int[] nums) {
        // 通过交换位置，进行排序, 排序可以直接用java 提供的函数
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] != i + 1 // 当前位置，不等与 i + 1 自己
                    && nums[nums[i] - 1] != nums[i]) { // 交换位置，不等于当前位置的值
                swap(nums, i, nums[i] - 1);
            }
        }

        // 计算重复值
        for (int i = 0; i < nums.length; i++) {
            // 符合当前位置，直接跳过
            if (nums[i] == i + 1) {
                continue;
            }
            //把重复的数字 和当前数组 +1 替换数组
            return new int[]{nums[i], i + 1};
        }

        // 不符合条件
        return null;
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }


    /**
     * 数组的度的定义是指数组里任一元素出现频数的最大值。
     * 找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。
     * 算法：
     *
     * 具有度数 d 的数组必须有一些元素 x 出现 d 次。如果某些子数组具有相同的度数，
     * 那么某些元素 x （出现 d 次）。最短的子数组是将从 x 的第一次出现到最后一次出现的数组。
     * 对于给定数组中的每个元素，让我们知道 left 是它第一次出现的索引； right
     * 是它最后一次出现的索引。例如，当 nums = [1,2,3,2,5] 时，left[2] = 1 和 right[2] = 3。
     * 然后，对于出现次数最多的每个元素 x，right[x] - left[x] + 1 将是我们的候选答案，我们将取这些候选的最小值。
     *
     */
    public int findShortestSubArray(int[] nums) {
        Map<Integer, Integer> left = new HashMap(),
                right = new HashMap(), count = new HashMap();

        for (int i = 0; i < nums.length; i++) {
            int x = nums[i];
            //记录 2 第一次出现的位置
            if (left.get(x) == null){
                left.put(x, i);
            }
            // 记录 2 第二次出现的位置
            right.put(x, i);
            // 计算2 出现的次数
            // 当集合中有这个key时 使用这个key的值 么有这个key 使用默认值  计算重复元素出现的次数
            count.put(x, count.getOrDefault(x, 0) + 1);
        }

        int ans = nums.length;
        int degree = Collections.max(count.values());
        for (int x: count.keySet()) {
            if (count.get(x) == degree) {
                ans = Math.min(ans, right.get(x) - left.get(x) + 1);
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        SolutionList solution = new SolutionList();

              solution.findShortestSubArray(new int[]{1,2,3,2,5});
//            int[] result = solution.findErrorNums(new int[]{4, 1, 2, 2});
//            System.out.println(Arrays.toString(result));

//        if (false) {
//            int[] result = solution.findErrorNums(new int[]{1, 2, 2, 4});
//            System.out.println(Arrays.toString(result));
//        }
//        if (true) {
//            int[] result = solution.findErrorNums(new int[]{2, 3, 2});
//            System.out.println(Arrays.toString(result));
//        }
    }
}
